// https://www.lintcode.com/problem/greatest-common-divisor/

public class Solution {
    /**
     * @param a: the given number
     * @param b: another number
     * @return: the greatest common divisor of two numbers
     */
    public int gcd(int a, int b) {
        // write your code here
        int x = Math.max(a, b);
        int y = Math.min(a, b);
        while ((x % y) != 0) {
            int tmp = x % y;
            x = y;
            y = tmp;
        }
        return y;
    }
}